home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 4686 < prev    next >
Encoding:
Text File  |  1996-08-05  |  8.7 KB  |  353 lines
  1. Path: newsbf02.news.aol.com!not-for-mail
  2. From: parhelion@aol.com (Parhelion)
  3. Newsgroups: comp.lang.c
  4. Subject: Dynamic array source - email if you find useful
  5. Date: 6 Feb 1996 09:11:14 -0500
  6. Organization: America Online, Inc. (1-800-827-6364)
  7. Sender: root@newsbf02.news.aol.com
  8. Message-ID: <4f7ni2$cge@newsbf02.news.aol.com>
  9. Reply-To: parhelion@aol.com (Parhelion)
  10.  
  11. /*************************************************************************
  12. ******
  13. dynarray.c Mark Atchison (parhelion@aol.com) 
  14.  
  15. By use of a linked list of row pointers and a linked list of column
  16. pointers for 
  17. each row, mimics behavior of a two-dimensional array, but is entirely
  18. dynamic.
  19. Created as a QuickWin app under MSVC 1.00, but should be portable.
  20.  
  21. Features:  Sparse in nature; only cells referenced w/ PutTableau are
  22. actually 
  23.             stored - GetTableau returns zero for all other
  24. values.
  25.            Will accept data in any order.
  26.            Does not use contiguous memory.
  27. Drawbacks: Slower access than static, speed degrades as array size
  28. increases. 
  29.            Consumes more memory than a static array - in x86 architecture,
  30.             a 5x10 static array of floats uses 200 bytes, while a dynamic
  31. array
  32.             would consume 430 bytes (assuming all elements are
  33. referenced).
  34. Usage:       Set ARRAYDATATYPE to desired numeric data type (could be
  35. adapted to 
  36.             pointers, with a little imagination)
  37.            Declare a DYANARRAYROW * (Tableau, in the example)
  38.            Call InitTableau to create first row instance
  39.            Place values in array using PutTableau
  40.            Retrieve values from array using GetTableau
  41. (uninitialzed cells = 0)
  42.            Free all links with FreeTableau 
  43. **************************************************************************
  44. *****/
  45. #include <stdlib.h>
  46. #include <stdio.h>
  47. #include <malloc.h>
  48. #include <string.h>
  49.  
  50. typedef int            BOOL;
  51. #define FALSE            0
  52. #define TRUE            1
  53.  
  54. #define ARRAYDATATYPE    float
  55.  
  56. typedef struct tagDynArrayRow DYNARRAYROW;
  57. typedef struct tagDynArrayCol DYNARRAYCOL;
  58.  
  59. struct tagDynArrayCol
  60. {
  61.   int             ColIndex;       
  62.   ARRAYDATATYPE ArrayValue;
  63.   DYNARRAYCOL     *NextCol_ptr;
  64. };
  65.  
  66. struct tagDynArrayRow
  67. {
  68.   int             RowIndex;
  69.   DYNARRAYCOL     *FirstCol_ptr;
  70.   DYNARRAYROW     *NextRow_ptr;
  71. };
  72.  
  73. BOOL InitTableau( DYNARRAYROW ** );
  74. BOOL PutTableau( DYNARRAYROW *, int, int, ARRAYDATATYPE );
  75. ARRAYDATATYPE GetTableau( DYNARRAYROW *, int, int );
  76. void FreeTableau( DYNARRAYROW * );
  77. void FreeColumns( DYNARRAYCOL * );
  78.  
  79. DYNARRAYROW * GetRow( DYNARRAYROW *, int );
  80. DYNARRAYCOL * GetCol( DYNARRAYCOL *, int );
  81.  
  82. int main()
  83. {
  84.     DYNARRAYROW *Tableau_ptr = NULL;
  85.     int R, C;
  86.     ARRAYDATATYPE ArrValue = 0;
  87.  
  88.     InitTableau ( &Tableau_ptr );            /* initialize
  89. first row entry */
  90.      
  91.     /* place values in the array */
  92.     for (R = 0; R < 3; R++)               
  93.     {
  94.         for (C = 0; C < 3; C++)
  95.         {
  96.             ArrValue++;
  97.             PutTableau( Tableau_ptr, R, C, ArrValue );
  98.         }
  99.     }
  100.       
  101.    /* retrieve and print array values */
  102.    for (R = 0; R < 3; R++)               
  103.    {
  104.         for (C = 0; C < 3; C++)
  105.         {
  106.               printf( "\n%d, %d = %f", R, C, GetTableau(
  107. Tableau_ptr, R, C ) );
  108.         }
  109.    }
  110.  
  111.     FreeTableau ( Tableau_ptr );             /* Free all linked memory
  112. */
  113.     return (0);
  114. }                   
  115. /*************************************************************************
  116. ****
  117. * I n i t T a b l e a u 
  118. *
  119. **************************************************************************
  120. ****/
  121.  
  122. BOOL InitTableau( DYNARRAYROW **Tableau_ptr)
  123. {
  124.     *Tableau_ptr = (struct tagDynArrayRow *)
  125. malloc(sizeof(DYNARRAYROW));
  126.     if ( *Tableau_ptr == NULL )                
  127.         return ( FALSE );               /*no memory available for
  128. first row  */
  129.      (*Tableau_ptr)->NextRow_ptr = NULL;    /*initialize ptr to next
  130. row         */
  131.      (*Tableau_ptr)->FirstCol_ptr = NULL;/*initialize ptr to first
  132. column     */
  133.     return ( TRUE );
  134. }
  135. /*************************************************************************
  136. ****
  137. * P u t T a b l e a u 
  138. *
  139. **************************************************************************
  140. ****/
  141.  
  142. BOOL PutTableau( DYNARRAYROW *Tableau_ptr, int R, int C, ARRAYDATATYPE
  143. ArrValue )
  144. {
  145.  
  146.     DYNARRAYROW *Row_ptr = NULL;
  147.     DYNARRAYROW *NewRow_ptr = NULL;
  148.     DYNARRAYCOL *Col_ptr = NULL;
  149.     DYNARRAYCOL *NewCol_ptr = NULL;
  150.  
  151.     /*get the exact row or the last row in the link */
  152.     Row_ptr = GetRow ( Tableau_ptr, R );
  153.     
  154.     if ( Row_ptr->FirstCol_ptr == NULL )/*create first row, if no row
  155. existed*/
  156.     {
  157.         Row_ptr->RowIndex = R;            /*record the row
  158. index value         */
  159.         Row_ptr->NextRow_ptr = NULL;    /*and set next row to NULL
  160.           */
  161.         
  162.         Row_ptr->FirstCol_ptr = (struct tagDynArrayCol *)
  163. malloc(sizeof(DYNARRAYCOL));
  164.  
  165.         if ( Row_ptr->FirstCol_ptr == NULL )        
  166.     
  167.             return ( FALSE );           /*no memory available
  168. for first col  */
  169.  
  170.         Row_ptr->FirstCol_ptr->ColIndex = C;
  171.         Row_ptr->FirstCol_ptr->ArrayValue = ArrValue;
  172.         Row_ptr->FirstCol_ptr->NextCol_ptr = NULL;
  173.         return ( TRUE );        
  174.     }                                  
  175.  
  176.     /*determine if requested row was found  */
  177.     if ( Row_ptr->RowIndex == R )        /*if this is requested row
  178.           */
  179.     {
  180.         Col_ptr = GetCol ( Row_ptr->FirstCol_ptr, C );
  181.         if ( Col_ptr->ColIndex == C )        
  182.         {
  183.             Col_ptr->ArrayValue = ArrValue;
  184.         }
  185.         else                        
  186.     
  187.         {
  188.             NewCol_ptr = (struct tagDynArrayCol *)
  189. malloc(sizeof(DYNARRAYCOL));
  190.  
  191.             if ( NewCol_ptr == NULL )        
  192.     
  193.                 return ( FALSE );       /*no memory
  194. available for next column*/
  195.  
  196.                Col_ptr->NextCol_ptr = NewCol_ptr;
  197.         
  198.             Col_ptr = NewCol_ptr;        /*move to the new column      
  199.       */
  200.         
  201.             Col_ptr->ColIndex = C;        /*record the column index
  202. value      */
  203.             Col_ptr->NextCol_ptr = NULL;/*and set next column
  204. to NULL        */
  205.             Col_ptr->ArrayValue = ArrValue;
  206.         }
  207.     }
  208.     else                            
  209. /*add the row and first column       */
  210.     {
  211.         NewRow_ptr = (struct tagDynArrayRow *)
  212. malloc(sizeof(DYNARRAYROW));
  213.  
  214.         if ( NewRow_ptr == NULL )                
  215.             return ( FALSE );           /*no memory available
  216. for next row   */
  217.  
  218.         Row_ptr->NextRow_ptr = NewRow_ptr;
  219.         
  220.         Row_ptr = NewRow_ptr;            /*move to the new row     
  221.           */
  222.         
  223.         Row_ptr->RowIndex = R;            /*record the row index
  224. value         */
  225.         Row_ptr->NextRow_ptr = NULL;    /*and set next row to NULL
  226.           */
  227.         
  228.         Row_ptr->FirstCol_ptr = (struct tagDynArrayCol *)
  229. malloc(sizeof(DYNARRAYCOL));
  230.  
  231.         if ( Row_ptr->FirstCol_ptr == NULL )        
  232.     
  233.             return ( FALSE );           /*no memory for first
  234. col of row     */
  235.  
  236.         Row_ptr->FirstCol_ptr->ColIndex = C;
  237.         Row_ptr->FirstCol_ptr->ArrayValue = ArrValue;
  238.         Row_ptr->FirstCol_ptr->NextCol_ptr = NULL;
  239.     }    
  240.     
  241.     return( TRUE );
  242. }
  243. /*************************************************************************
  244. ****
  245. * G e t T a b l e a u 
  246. *
  247. **************************************************************************
  248. ****/
  249.  
  250. ARRAYDATATYPE GetTableau( DYNARRAYROW *Tableau_ptr, int R, int C )
  251. {
  252.  
  253.     DYNARRAYROW *Row_ptr = NULL;
  254.     DYNARRAYCOL *Col_ptr = NULL;
  255.  
  256.     /*find the exact row requested or return the last row in the list 
  257. */
  258.     Row_ptr = GetRow ( Tableau_ptr, R );
  259.     if ( Row_ptr->RowIndex != R)            /*if not exact row
  260. return 0     */
  261.         return ( 0 );    
  262.  
  263.     /*find the column in the row */
  264.     Col_ptr = GetCol ( Row_ptr->FirstCol_ptr, C );
  265.     if ( Col_ptr->ColIndex != C)            /*if not exact col return
  266. 0     */
  267.         return ( 0 );    
  268.  
  269.     return ( Col_ptr->ArrayValue );
  270. }
  271. /*************************************************************************
  272. ****
  273. * G e t R o w 
  274. *
  275. **************************************************************************
  276. ****/
  277.  
  278. DYNARRAYROW * GetRow( DYNARRAYROW *Row_ptr, int R )
  279. {
  280.     DYNARRAYROW *tmp_ptr = Row_ptr;
  281.  
  282.       while( tmp_ptr->RowIndex != R )        /*return exact row or last
  283. in list  */
  284.     {
  285.         if ( tmp_ptr->NextRow_ptr == NULL )
  286.             return ( tmp_ptr );
  287.         tmp_ptr = tmp_ptr->NextRow_ptr;
  288.     }
  289.     return ( tmp_ptr );
  290. }
  291.  
  292. /*************************************************************************
  293. ****
  294. * G e t C o l 
  295. *
  296. **************************************************************************
  297. ****/
  298.  
  299. DYNARRAYCOL * GetCol( DYNARRAYCOL *Col_ptr, int C )
  300. {
  301.     DYNARRAYCOL *tmp_ptr = Col_ptr;
  302.  
  303.       while( tmp_ptr->ColIndex != C )        /*return exact col or last
  304. in list  */
  305.     {
  306.         if ( tmp_ptr->NextCol_ptr == NULL )
  307.             return ( tmp_ptr );
  308.          tmp_ptr = tmp_ptr->NextCol_ptr;
  309.    }
  310.     return ( tmp_ptr );
  311. }
  312.  
  313. /*************************************************************************
  314. ****
  315. * F r e e T a b l e a u  
  316. *
  317. **************************************************************************
  318. ****/
  319.  
  320. void FreeTableau( DYNARRAYROW *Row_ptr )
  321. {
  322.     DYNARRAYROW *tmp_ptr;
  323.  
  324.     while ( Row_ptr != NULL )
  325.     {
  326.         FreeColumns ( Row_ptr->FirstCol_ptr );   
  327.         tmp_ptr = Row_ptr->NextRow_ptr;
  328.         free ( Row_ptr );
  329.         Row_ptr = tmp_ptr;
  330.     }
  331.     return;
  332. }
  333.  
  334. /*************************************************************************
  335. ****
  336. * F r e e C o l u m n  
  337. *
  338. **************************************************************************
  339. ****/
  340.  
  341. void FreeColumns( DYNARRAYCOL *Col_ptr )
  342. {
  343.     DYNARRAYCOL *tmp_ptr;
  344.  
  345.     while ( Col_ptr != NULL )
  346.     {
  347.         tmp_ptr = Col_ptr->NextCol_ptr;
  348.         free ( Col_ptr );
  349.         Col_ptr = tmp_ptr;
  350.     }
  351.     return;
  352. }
  353.